package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName LC279
 * @Description: TODO
 * @Author hl
 * @Date 2020/8/13
 * @Version V1.0
 **/
public class LC279 {
    public int numSquares(int n) {
        ArrayList<Integer> Se=find(n);
        Queue<Integer> queue=new LinkedList<>();
        boolean[] visited=new boolean[n+1];
        queue.add(n);
        int step=0;
        while(!queue.isEmpty()){
            step++;
            int size=queue.size();
            while(size-->0){
                int num=queue.poll();
                for(int i=Se.size()-1;i>=0;i--){
                    if(num-Se.get(i)<0){
                        continue;
                    }
                    if(num-Se.get(i)==0){
                        return step;
                    }
                    visited[num]=true;
                    queue.add(num-Se.get(i));

                }
            }
        }
        return  n;
    }
    public ArrayList<Integer> find(int n){
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=1;i<=n/2;i++){
            if(i*i<=n){
                list.add(i);
            }else{
                return list;
            }
        }
        return  list;
    }
}
